package cn.mayday.algorithms.year2021.month1.D快慢指针;

/**
 * @author Mayday05
 * @date 2020/8/8 17:15
 * <p>
 * 链表中倒数第k个节点
 */
public class ArrorSolution22 {

    /**
     * 总结：
     */
    public static void main(String[] args) {
        ArrorSolution22 solution22 = new ArrorSolution22();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode result = solution22.getKthFromEnd(node1, 2);

        System.out.println("++++++ result ++++++++++" + result.toString());
    }

    /**
     * 链表中倒数第k个节点
     *
     * 快慢指针，先让快指针走k步，然后两个指针同步走，当快指针走到头时，
     *
     * 慢指针就是链表倒数第k个节点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode frontNode = head, behindNode = head;
        while (frontNode != null && k > 0) {
            frontNode = frontNode.next;
            k--;
        }

        while (frontNode != null) {
            frontNode = frontNode.next;
            behindNode = behindNode.next;
        }

        return behindNode;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
